package cn.edu.nju.ws.aquila.rdf.canonicalization;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;

import cn.edu.nju.ws.aquila.rdf.canonicalization.comparator.RDFGraphComparator;
import cn.edu.nju.ws.aquila.rdf.canonicalization.comparator.RDFGraphsComparator;
import cn.edu.nju.ws.aquila.rdf.canonicalization.comparator.StatementComparator;
import cn.edu.nju.ws.aquila.rdf.canonicalization.labeled.LabeledRDFGraph;
import cn.edu.nju.ws.aquila.rdf.canonicalization.labeled.LabeledResource;
import cn.edu.nju.ws.aquila.util.MD5;

/**
 * @author Gong Cheng
 * 
 */
public class Canonicalizer {
	private Comparator<LabeledResource> labeledResourceCompartor = null;

	private Canonicalizer() {
		/* Nothing */
	}

	public Canonicalizer(Comparator<LabeledResource> labeledResourceCompartor) {
		this.labeledResourceCompartor = labeledResourceCompartor;
	}

	/**
	 * Canonicalize an RDF graph
	 * 
	 * @param labeledRDFGraph
	 * @param md5
	 * @return
	 */
	public byte[] canonicalizeRDFGraph(LabeledRDFGraph labeledRDFGraph, MD5 md5) {
		/* Relabeling */
		this.relabelBNodesByContextIteration(labeledRDFGraph);

		/* Uniquely labeling blank nodes */
		ArrayList<LabeledResource> labeledBNodes = new ArrayList<LabeledResource>();
		for (Iterator<LabeledResource> lrs = labeledRDFGraph
				.listLabeledResources(); lrs.hasNext();) {
			LabeledResource lr = lrs.next();
			if (lr.getRDFNode().isAnon()) {
				labeledBNodes.add(lr);
			}
		}

		Collections.sort(labeledBNodes, this.labeledResourceCompartor);

		for (int i = 0; i < labeledBNodes.size(); i++) {
			labeledBNodes.get(i).setLabel(i + 1);
		}
		labeledBNodes.clear();
		labeledBNodes = null;

		/* Firstly MD5 each statement */
		ArrayList<String> canonicalStrings = new ArrayList<String>(
				labeledRDFGraph.getLabeledStatements().size());
		for (ArrayList<LabeledResource> ls : labeledRDFGraph
				.getLabeledStatements()) {
			StringBuffer buffer = new StringBuffer();
			buffer.append(ls.get(0).toString());
			buffer.append(" ");
			buffer.append(ls.get(1).toString());
			buffer.append(" ");
			buffer.append(ls.get(2).toString());

			md5.addString(buffer.toString());
			canonicalStrings.add(MD5.asHex(md5.getResult()));
		}

		/* Then MD5 their results (after sorting) */
		Collections.sort(canonicalStrings);
		for (int i = 0; i < canonicalStrings.size(); i++) {
			md5.addString(canonicalStrings.get(i));
		}
		canonicalStrings.clear();
		canonicalStrings = null;

		return md5.getResult();
	}

	/**
	 * Relabel blank nodes by context
	 * 
	 * @param labeledGraph
	 */
	private void relabelBNodesByContext(LabeledRDFGraph labeledGraph) {
		StatementComparator statementComparator = new StatementComparator(
				this.labeledResourceCompartor);
		RDFGraphComparator rdfGraphComparator = new RDFGraphComparator(
				statementComparator);
		RDFGraphsComparator rdfGraphsComparator = new RDFGraphsComparator(
				rdfGraphComparator);

		HashMap<Integer, ArrayList<LabeledResource>> label2NotUniquelyLabeledResources = new HashMap<Integer, ArrayList<LabeledResource>>();
		for (Iterator<LabeledResource> lrs = labeledGraph
				.listLabeledResources(); lrs.hasNext();) {
			LabeledResource lr = lrs.next();
			if (!lr.isUniquelyLabeled()) {
				Integer label = new Integer(lr.getLabel());
				ArrayList<LabeledResource> notUniquelyLabeledResources = label2NotUniquelyLabeledResources
						.get(label);
				if (notUniquelyLabeledResources == null) {
					notUniquelyLabeledResources = new ArrayList<LabeledResource>();
					label2NotUniquelyLabeledResources.put(label,
							notUniquelyLabeledResources);
				}
				notUniquelyLabeledResources.add(lr);
			}
		}

		HashMap<LabeledResource, Integer> lr2Label = new HashMap<LabeledResource, Integer>();
		/* For each label */
		for (Entry<Integer, ArrayList<LabeledResource>> entry : label2NotUniquelyLabeledResources
				.entrySet()) {
			HashMap<LabeledResource, ArrayList<ArrayList<ArrayList<LabeledResource>>>> lr2SOStmts = new HashMap<LabeledResource, ArrayList<ArrayList<ArrayList<LabeledResource>>>>();
			ArrayList<ArrayList<ArrayList<ArrayList<LabeledResource>>>> allSOStmts = new ArrayList<ArrayList<ArrayList<ArrayList<LabeledResource>>>>();
			for (LabeledResource lr : entry.getValue()) {
				ArrayList<ArrayList<ArrayList<LabeledResource>>> soStmts = new ArrayList<ArrayList<ArrayList<LabeledResource>>>(
						2);
				soStmts.add(new ArrayList<ArrayList<LabeledResource>>());
				soStmts.add(new ArrayList<ArrayList<LabeledResource>>());

				lr2SOStmts.put(lr, soStmts);
				allSOStmts.add(soStmts);
			}
			for (ArrayList<LabeledResource> ls : labeledGraph
					.getLabeledStatements()) {
				LabeledResource subj = ls.get(0);
				if (lr2SOStmts.containsKey(subj)) {
					lr2SOStmts.get(subj).get(0).add(ls);
				}
				LabeledResource obj = ls.get(2);
				if (lr2SOStmts.containsKey(obj)) {
					lr2SOStmts.get(obj).get(1).add(ls);
				}
			}

			for (ArrayList<ArrayList<ArrayList<LabeledResource>>> soStmts : lr2SOStmts
					.values()) {
				Collections.sort(soStmts.get(0), statementComparator);
				Collections.sort(soStmts.get(1), statementComparator);
			}
			Collections.sort(allSOStmts, rdfGraphsComparator);

			int candidateLabel = entry.getKey().intValue();
			int currLabel = 0;

			for (int i = 0; i < allSOStmts.size(); i++) {
				LabeledResource lr = null;
				ArrayList<ArrayList<ArrayList<LabeledResource>>> currSOStmts = allSOStmts
						.get(i);
				for (Entry<LabeledResource, ArrayList<ArrayList<ArrayList<LabeledResource>>>> entry1 : lr2SOStmts
						.entrySet()) {
					if (entry1.getValue() == currSOStmts) {
						lr = entry1.getKey();
						break;
					}
				}

				if (i > 0) {
					ArrayList<ArrayList<ArrayList<LabeledResource>>> prevSOStmts = allSOStmts
							.get(i - 1);
					if (rdfGraphsComparator.compare(currSOStmts, prevSOStmts) != 0) {
						currLabel = candidateLabel;
					}
				} else {
					currLabel = candidateLabel;
				}
				lr2Label.put(lr, new Integer(currLabel));

				if (currLabel == candidateLabel) {
					if (i < allSOStmts.size() - 1) {
						ArrayList<ArrayList<ArrayList<LabeledResource>>> nextSOStmts = allSOStmts
								.get(i + 1);
						if (rdfGraphsComparator.compare(currSOStmts,
								nextSOStmts) != 0) {
							lr.setUniquelyLabeled();
						}
					} else {
						lr.setUniquelyLabeled();
					}
				}

				candidateLabel++;
			}

			for (ArrayList<ArrayList<ArrayList<LabeledResource>>> soStmts : lr2SOStmts
					.values()) {
				for (ArrayList<ArrayList<LabeledResource>> lss : soStmts) {
					lss.clear();
				}
				soStmts.clear();
			}
			lr2SOStmts.clear();
			lr2SOStmts = null;
			allSOStmts.clear();
			allSOStmts = null;
			entry.getValue().clear();
		}

		label2NotUniquelyLabeledResources.clear();
		label2NotUniquelyLabeledResources = null;
		for (Entry<LabeledResource, Integer> entry : lr2Label.entrySet()) {
			entry.getKey().setLabel(entry.getValue().intValue());
		}
		lr2Label.clear();
		lr2Label = null;
		rdfGraphsComparator.close();
		rdfGraphsComparator = null;
		rdfGraphComparator.close();
		rdfGraphComparator = null;
		statementComparator.close();
		statementComparator = null;
	}

	/**
	 * Relabel blank nodes by context (iteratively)
	 * 
	 * @param labeledRDFGraph
	 */
	private void relabelBNodesByContextIteration(LabeledRDFGraph labeledRDFGraph) {
		int lastLabelSum = 0;
		while (true) {
			this.relabelBNodesByContext(labeledRDFGraph);

			boolean allDone = true;
			int labelSum = 0;
			for (Iterator<LabeledResource> lrs = labeledRDFGraph
					.listLabeledResources(); lrs.hasNext();) {
				LabeledResource lr = lrs.next();
				if (!lr.isUniquelyLabeled()) {
					allDone = false;
				}
				labelSum += lr.getLabel();
			}

			if (allDone || labelSum == lastLabelSum) {
				break;
			}
			lastLabelSum = labelSum;
		}
	}

	public void close() {
		this.labeledResourceCompartor = null;
	}
}